//== SAGITTARIUS ============================================================================

//== BEGINNING OF CODE ===============================================================

#include "sagittarius/core/SagittariusCore.h"
#include SAGITTARIUS_GREYLIST_IMPLH
#include "sagittarius/parallel/atomics.h"
#include "sagittarius/io/io.h"
#include <malloc.h>
#include <stddef.h>
//#include <string.h>

greylist_seg* create_new_greylist_seg() {
    greylist_seg* s=malloc(sizeof(greylist_seg));
    s->l = GREYLIST_BLOCK_N;
    s->a = malloc(s->l*sizeof(sg_glr));
    s->hd = s->a;
    s->tl = s->hd+1; //when head = tail it means the buffer is full
    s->hd->nxt = s->tl;
    s->tl->nxt = NULL;
    s->nxt = NULL;
    return s;
}

void destroy_greylist_seg(greylist_seg* s) {
    free(s->a);
    free(s);
}

#define GREYLIST_PUSH_SUCCESS 0
//#define GREYLIST_RETRY 1
#define GREYLIST_NEW_SEG 1

int greylist_seg_push(greylist_seg* gs, void* p) {
    sg_glr *tl, *nxt;
    
    while(1) {
        tl = gs->tl;
        if(tl == gs->hd)
            //tail caught up to head - need to allocate new segment
            return GREYLIST_NEW_SEG;
        nxt = tl+1; //next link
        if(nxt > gs->a+gs->l)
            nxt = gs->a; //wrap (circ. buf)
        //tl and nxt are always consistent in this system because
        //nxt is based solely on the value of tl
        //this code isn't harmful but it's not necessary
        //if(tl != gs->tl) //make sure tl and nxt are consistent
            //continue;
        //try to take this slot
        if(sg_casptr(tl->nxt, NULL, nxt)) {
            //success: acquired ownership of this node
            //try to advance tail
            sg_casptr(gs->tl, tl, nxt);
            //insert data field
            tl->v = p;
            return GREYLIST_PUSH_SUCCESS;
        } else {
            //someone else took it
            //try to advance tail
            sg_casptr(&gs->tl, tl, nxt);
        }
    }
}

void* greylist_seg_pop(greylist_seg* gs) {
    sg_glr *hd, *tl, *nxt;
    void* v;
    
    while(1) {
        tl = gs->tl;
        if(tl->nxt) {
            //tail is falling behind; try to advance it
            sg_casptr(gs->tl, tl, tl->nxt);
            continue; //try again
        }
        hd = gs->hd;
        nxt = hd->nxt; //next link
        v= hd->v;
        //checked by cas
        if(hd != gs->hd) //make sure hd and nxt are consistent
            //ABA hazard, but in the event that hd really is gs->hd
            //(whether ABA occurred or not), it is valid to pop it
            continue;
        if(nxt == tl)
            //empty queue
            return NULL;
        if(sg_casptr(&gs->hd, hd, nxt)) {
            return v;
        }
    }
}

void init_greylist(greylist_t* gl) {
    //INITSEMA(gl->sema);
    //WLSEMA(gl->sema);
    
    gl->n = 1;
    gl->hd = create_new_greylist_seg();
    
    //WUSEMA(gl->sema);
}

void finalize_greylist(greylist_t* gl) {
    greylist_seg *s, *t;
    s = gl->hd;
    t = s;
    while(s) {
        s = s->nxt;
        destroy_greylist_seg(t);
        t = s;
    }
}

void greylist_push(greylist_t* gl, void* p) {
    //int res;
    greylist_seg *tl, *nxt, *newseg;
    
    while(1) {
        tl = gl->tl;
        nxt = tl->nxt;
        if(tl != gl->tl)
            //make sure tl and nxt are consistent
            continue;
        if(nxt && (SG_POINTER_UINT)nxt != 0xffffffff)
            //tail is falling behind; try to advance it
            sg_casptr(&gl->tl, tl, nxt);
        if(!greylist_seg_push(tl, p)) {
            return;
        } else {
            //need to allocate a new segment
            AT(gl->n < 100, "I think you're allocating too much");
            if(sg_casptr(&tl->nxt, NULL, 0xffffffff)) {
                newseg = create_new_greylist_seg();
                //append this new segment to the linked list
                while(1) {
                    if((SG_POINTER_UINT)nxt == 0xffffffff && sg_casptr(&tl->nxt, 0xffffffff, newseg)) {
                        //try to advance tail
                        sg_casptr(&gl->tl, tl, newseg);
                    }
                }
            }
        }
    }
}

void* greylist_pop(greylist_t* gl) {
    greylist_seg *hd, *nxt;
    void* v;
    
    while(1) {
        hd = gl->hd;
        v = greylist_seg_pop(hd);
        if(v)
            return v;
        //else, head is empty
        nxt = hd->nxt;
        if(hd != gl->hd)
            //make sure hd and nxt are consistent
            continue;
        if(!nxt)
            //the whole list is empty
            return NULL;
        //try to advance head
        sg_casptr(&gl->hd, hd, nxt);
    }
}

void dump_greylist(int fd, greylist_t* gl) {
    greylist_seg* s;
    SG_WRITE(fd, "Grey list\n");
    SG_WRITE(fd, "  Head: ");
    sg_writePtr(fd, gl->hd);
    SG_WRITE(fd, "\n  Tail: ");
    sg_writePtr(fd, gl->tl);
    SG_WRITE(fd, "\n");
    for(s = gl->hd; s!=gl->tl;) {
        /*SG_WRITE(fd, "\n    Record ");
        sg_writePtr(fd, p);
        SG_WRITE(fd, ":\n");
        SG_WRITE(fd, "\n      ");
        sg_writePtr(fd, p->v);
        ++p;
        if(p == gl->r + gl->n)
            p = gl->r;*/
    }
}
